package com.kehao.leetcode.jzoffer;

import org.junit.Test;

import java.util.*;

/**
 * @author Kehao.Chen
 * @version 1.0
 * @date 2022/6/8 15:50
 */
public class JZSolution007 {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 2; i < nums.length; i++) {
            map.put(nums[i],i);
        }
        for (int i = 0; i < nums.length-2; i++) {
            if(i!=0&&nums[i-1]==nums[i]){
                continue;
            }
            for (int j = i+1; j < nums.length-1; j++) {
                if(j!=i+1 && nums[j]==nums[j-1]){
                    continue;
                }
                int want = nums[i] + nums[j];
                Integer k = map.get(-want);
                if(k !=null&& k >j){
                    List<Integer> item = new ArrayList<>();
                    item.add(nums[i]);
                    item.add(nums[j]);
                    item.add(nums[k]);
                    result.add(item);
                }
            }
        }
        return result;
    }

    @Test
    public void test01(){
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(threeSum(nums));
    }
}
